/*
 * @lc app=leetcode.cn id=803 lang=javascript
 *
 * [803] 打砖块
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @param {number[][]} hits
 * @return {number[]}
 */
var hitBricks = function (grid, hits) {
  const m = grid.length;
  const n = grid[0].length;
  const unionFind = new UnionFind(m * n + 1);

  // 复制grid，保存状态
  const copy = JSON.parse(JSON.stringify(grid));
  for (let i = 0; i < hits.length; i++) {
    const [x, y] = hits[i];
    copy[x][y] = 0;
  }
  // 构建并查集
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (copy[i][j] === 1) {
        // 连接屋顶
        if (i === 0) {
          unionFind.union(m * n, i * n + j);
        }
        if (i > 0 && copy[i - 1][j] === 1) {
          unionFind.union(i * n + j, (i - 1) * n + j);
        }
        if (j > 0 && copy[i][j - 1] === 1) {
          unionFind.union(i * n + j, i * n + j - 1);
        }
      }
    }
  }

  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const result = new Array(hits.length).fill(0);
  // 逆序补回砖块
  for (let i = hits.length - 1; i >= 0; i--) {
    const [x, y] = hits[i];
    // 如果hit的砖块为0，跳过
    if (grid[x][y] === 0) {
      continue;
    }
    // 补回之前屋顶的出点
    const prev = unionFind.count(m * n);
    if (x === 0) {
      unionFind.union(y, m * n);
    }

    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;
      if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
        if (copy[nx][ny] === 1) {
          unionFind.union(x * n + y, nx * n + ny);
        }
      }
    }
    // 补回之后屋顶的出点
    const count = unionFind.count(m * n);
    // 有可能是负数
    result[i] = Math.max(0, count - prev - 1);
    copy[x][y] = 1;
  }
  return result;
};
class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((_, idx) => idx);
    this.size = new Array(n).fill(1);
  }
  find(x) {
    if (x !== this.parent[x]) {
      this.parent[x] = this.find(this.parent[x]);
    }

    return this.parent[x];
  }
  union(x, y) {
    const ux = this.find(x);
    const uy = this.find(y);

    if (ux ^ uy) {
      this.parent[ux] = uy;
      this.size[uy] += this.size[ux];
    }
  }
  count(x) {
    return this.size[this.find(x)];
  }
}
// @lc code=end
